package com.github.tangmonkmeat;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;

/**
 * Description:
 *
 * @author zwl
 * @version 1.0
 * @date 2021/7/28 下午2:00
 */
public class 填充每个节点的下一个右侧节点指针 {

    public static void main(String[] args) {

        //String a = "123";
        //
        //String b = new String("123");
        //
        //System.out.println(a.hashCode());
        //
        //// String 类型的hashcode 是由内容生成的
        //// 所以，内容相同的 String类型的对象，hashcode必然相同
        //System.out.println(b.hashCode());
        //
        //// String类型的equals方法，也是会比较内容的
        //System.out.println(a.equals(b));
        //
        //// 所以，保证了：具有相同内容的String对象，equals和hashcode是相同的
        //System.out.println("");

        Map<String, Object> map = new HashMap<>(4);
        map.put(null,123);

        map.put(null,321);

        Object o = map.get(null);

        System.out.println(o);

        System.out.println("");


        //Node root = new Node(1);
        //Node node2 = new Node(2);
        //Node node3 = new Node(3);
        //Node node4 = new Node(4);
        //Node node5 = new Node(5);
        //Node node6 = new Node(6);
        //Node node7 = new Node(7);
        //
        //root.left = node2;
        //root.right = node3;
        //
        //node2.left = node4;
        //node2.right = node5;
        //
        //node3.left = node6;
        //node3.right = node7;
        //
        //
        //
        //connect(root);

    }

    public static Node connect(Node root) {
        ArrayList<Node> rowStack1 = new ArrayList<>();
        LinkedList<Node> rowStack2 = new LinkedList<>();
        rowStack1.add(root);
        rowStack2.add(root);

        while(!rowStack2.isEmpty()){
            // 设置next
            for(int i = 0;i < rowStack1.size() - 1;i++){
                Node node = rowStack1.get(i);
                node.next = rowStack1.get(i + 1);
            }
            rowStack1.get(rowStack1.size() - 1).next = null;


            Node first = rowStack2.getFirst();
            if (first.left == null && first.right == null){
                break;
            }
            // 子节点
            int len = rowStack2.size();
            int z = 0;
            for(int j = 0;j < len;j++){
                Node node = rowStack2.pop();
                rowStack2.add(node.left);
                rowStack2.add(node.right);

                if (z < len){
                    rowStack1.set(z++,node.left);
                }else{
                    rowStack1.add(z++,node.left);
                }

                if (z < len){
                    rowStack1.set(z++,node.right);
                }else {
                    rowStack1.add(z++,node.right);
                }
            }
        }
        return root;
    }

    static class Node {
        public int val;
        public Node left;
        public Node right;
        public Node next;

        public Node() {}

        public Node(int _val) {
            val = _val;
        }

        public Node(int _val, Node _left, Node _right, Node _next) {
            val = _val;
            left = _left;
            right = _right;
            next = _next;
        }
    };

}
